package com.qch.leecode.cyc2018.algorithm.a1_double_pointer;

import com.qch.leecode.cyc2018.util_comom.Common;

/**
 * 算法思想：双指针：633.两数平方和
 *  https://leetcode.cn/problems/sum-of-square-numbers/
 *  自己思路缺点：没有利用开方后的整数，就不需要重新开辟地址
 *
 * @Author qch
 * @Date 2022/11/7
 *
 * 题目：给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c
 * 输入：c = 5
 * 输出：true
 * 解释：1 * 1 + 2 * 2 = 5
 *
 * 解题思路：
 * 目标为了找整数的平方，因此target可以为i^2的值
 * i=0,j=sqrt(target) 开平方
 * 注意：空间的占用，不另用数组存放i
 *
 * 2147483600 该用例测试不通过
 */
public class L2_SumSquare633 {
    public static void main(String[] args) {
        boolean b = good_judgeSquareSum(5);
        System.out.println(b);
    }
    public static boolean good_judgeSquareSum(int target) {
        if (target<0)
            return false;
        int i=0;
        int j= (int) Math.sqrt(target);
        while (i<=j)
        {
            int sum=i*i+j*j;
            if(sum==target)
            {
                return true;
            }else if(sum>target)
            {
                j--;
            }else {
                i++;
            }
        }
        return false;
    }
    public static boolean error_own_judgeSquareSum(int c) {
        int[] nums=new int[c];
        for (int i=0;i<c;i++)
        {
            nums[i]=i+1;
        }
        System.out.println(Common.toString(nums));
        int i=0;
        int j=c-1;
        while (i<j)
        {
            int sum=nums[i]*nums[i]+nums[j]*nums[j];
            int val=c*c;
            if(sum==val)
            {
                return true;
            }else if(sum>val)
            {
                j--;
            }else {
                i++;
            }
        }
        return false;
    }
}
